UOJ62【UR#5】怎样跑得更快 <莫比乌斯反演>

Problem

【UR #5】怎样跑得更快

时间限制：
空间限制：
大力水手问禅师：“大师，我觉得我光有力气是不够的。比如我吃菠菜可以让力气更大，但是却没有提升跑步的速度。请问怎样才能跑得更快？我试过吃白菜，没有效果。”
禅师浅笑，答：“方法很简单，不过若想我教你，你先看看这道的题。”
令（，一个质数）。
给你整数。现在有整数和满足，且对于满足：

其中表示和除以的余数相等。表示和的最大公约数，表示和的最小公倍数。
有个询问，每次给出，请你解出的值。

输入格式

第一行四个整数。保证。
接下来行，每行个整数依次表示。保证。

输出格式

共行，每行对给出的，输出对应的。
如果有多组解输出任意一组即可。
如果无解那么这一行只用输出一个整数。

样例输入输出

样例一

Input

1
2
3

3 1 0 2
1 0 0
1 2 3

Output

1 2	499122179 998244352 499122176 998244352 1 1

Explanation
对于第一个询问，要满足的等式为：

样例二

见样例数据下载。

限制与约定

对于所有数据，，。

测试点编号			其他


			保证有唯一解

			保证有唯一解
			保证有唯一解

			保证有唯一解


			无

后记

还没听完题，大力水手就嘶吼着：“太难了我不会我不会！”，飞快地跑掉了。
禅师看着大力水手消失的背影，叹了口气说：“你们这些人啊，每天就想做些大水题，一碰到难题，跑得不知道比谁都快。”
后来大力水手把的题题面贴在了汽车的后挡风玻璃上，人类从此掌握了光速旅行的正确方式。

下载

样例数据下载

标签：莫比乌斯反演

Solution

先膜一发vfk的题解。

首先将题目中的式子转换一下：

设，那么原式化为

此时可以强行”说一句废话“来加入反演。存在数论函数使得，那么，这样若知道，即可枚举约数求出，即

for (int i = 1; i <= n; i++) fr[i] = f[i];
for (int i = 1; i <= n; i++)
    for (int j = i+i; j <= n; j += i)
        fr[j] -= fr[i];

将带入原式即可得到

令，，那么

我们知道右边，要求左边，于是再次做反演，即，即

for (int i = 1; i <= n; i++) fz[i] = b[i]*Pow(g(i), P-2);
for (int i = 1; i <= n; i++)
    for (int j = i+i; j <= n; j += i)
        fz[j] -= fz[i];

这样就得到了的值，即得到的值，于是即可算出的值。
然后再尝试用推出。由于，设，那么。
仍然是反演的形式，再次反演得到，即

for (int i = 1; i <= n; i++) hx[i] = z[d];
for (int i = n; i >= 1; i--)
    for (int j = i+i; j <= n; j += i)
        hx[i] -= hx[j];

知道了，即可由求出的值。

总结一下，分为三次反演：

预处理的值（线性筛），反演求
读入，反演求，乘的逆元即可得到
通过反演求，乘的逆元即可得到

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define P 998244353
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, c, d, q, b[MAX_N+5], x[MAX_N+5];
lnt g[MAX_N+5], fr[MAX_N+5], fz[MAX_N+5], hx[MAX_N+5];
int cnt, pri[MAX_N+5]; bool NotPri[MAX_N+5];
inline lnt Pow(lnt x, int k) {
    lnt ret = 1; bool flag = (k < 0);
    for (k = abs(k); k; k >>= 1, (x *= x) %= P)
        if (k&1) (ret *= x) %= P;
    return flag ? Pow(ret, P-2) : ret;
}
void init() {
    fr[1] = g[1] = NotPri[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!NotPri[i])
            pri[cnt++] = i, fr[i] = Pow(i, c-d), g[i] = Pow(i, d);
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > n) break;
            NotPri[i*pri[j]] = true;
            fr[i*pri[j]] = fr[i]*fr[pri[j]]%P;
            g[i*pri[j]] = g[i]*g[pri[j]]%P;
            if (i%pri[j] == 0) break;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = i+i; j <= n; j += i)
            (fr[j] += (P-fr[i])) %= P;
}
int main() {
    read(n), read(c), read(d), read(q), init();
    for (bool flag = false; q--; flag = false) {
        for (int i = 1; i <= n; i++) read(b[i]);
        for (int i = 1; i <= n; i++)
            fz[i] = 1LL*b[i]*Pow(g[i], P-2)%P;
        for (int i = 1; i <= n; i++)
            for (int j = i+i; j <= n; j += i)
                (fz[j] += (P-fz[i])) %= P;
        for (int i = 1; i <= n; i++)
            if (!fr[i] && fz[i]) flag = true;
        if (flag) {puts("-1"); continue;}
        for (int i = 1; i <= n; i++)
            hx[i] = fz[i]*Pow(fr[i], P-2)%P;
        for (int i = n; i >= 1; i--)
            for (int j = i+i; j <= n; j += i)
                (hx[i] += (P-hx[j])) %= P;
        for (int i = 1; i <= n; i++)
            x[i] = (int)(hx[i]*Pow(g[i], P-2)%P);
        for (int i = 1; i <= n; i++) printf("%d ", x[i]); puts("");
    }
    return 0;
}